TIFR CSE 2014 | Part B | Question: 10

Question

Given a set of $n$ distinct numbers, we would like to determine both the smallest and the largest number. Which of the following statements is TRUE?

• A. These two elements can be determined using $O\left(\log^{100}n\right)$ comparisons.
• B. $O\left(\log^{100}n\right)$ comparisons do not suffice, however these two elements can be determined using $n + O(\log n)$ comparisons.
• C. $n+O(\log n)$ comparisons do not suffice, however these two elements can be determined using $3\lceil n/2 \rceil$ comparisons.
• D. $3\lceil n/2 \rceil$ comparisons do not suffice, however these two elements can be determined using $2(n - 1)$ comparisons.
• E. None of the above.

Comments

The divide and conquer algorithm for finding the min and max elements of a list operates in worst case $3n/2 - 2$ comparisons. It is described in Sartaj Sahni's algorithms book.

---

Thanks.

---

To find the smallest and the second smallest element (and the third smallest.. so on), it is $n + O(n)$ (See this and this)

To find the maximum and the minimum element, $ceil(3n/2)-2$

---

Answer 1

Answer will be C.

To be accurate, it will need $3n/2 -2$ comparisons .

Comments

It is true for n=2 in my opinion. can you tell where it is wrong??

---

@sushmita comment,

for even numbers- 1.5n-2

for odd- 3/2(n-1) Comparisons

it basically keeps you away from fraction and give positive integers (positive whole numbers) . 

any even number multiply with .5 give whole number always.

now, for even – 1.5n making whole number

and in odd – (n-1) making it even and even multiply with 1.5 give whole number.

---

For odd it’ll be 3(n-2)/2 comps

Answer 2

Similar to the approach proposed by Himanshu1 here:

https://gateoverflow.in/27194/tifr2014-b-9

Construct a decision tree to determine the minimum element: $n - 1$ comparisons

Maximum element can be found from the same tree as it will be the biggest element out of $\frac{n}{2}$ elements at the first level which lost the decision: $\frac{n}{2} - 1$ comparisons

Therefore, the resultant number of comparisons: $3(\frac{n}{2}) - 2$, tighest bound on which is option (C).

Comments

@pranav Kant Gaur

Maximum element will at leaf na? and  at leaf there are n elements so comparison should be n-1. Please clear my doubt.

---

@Bad_Doctor

Yes maximum comparison will be for leaf.But question is asking for both maximim and minimum .

For maximum n-1 comparison

For minimum n-1 comparison

Total number of comparison=2*(n-1)

If you will draw the tree you will find that the leaf node level(is the last level) needs n/2 comparison.And it is common to both minimum and maximum.

So total number of comparison required=2*(n-1) -n/2 =(3/2)n-2 when n is even.

---

https://gateoverflow.in/27194/tifr2014-b-9

This is a rather good explanation.